package com.leetcode.test.linklist.classic;

import com.leetcode.test.linklist.ListNode;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/explore/learn/card/linked-list/195/classic-problems/754/
 */
public class 回文链表 {

	@Test
	public void test() {
//		输入: 1->2
//		输出: false
		ListNode n1 = new ListNode(1);
		ListNode n2 = n1.next = new ListNode(2);

		Assert.assertFalse(isPalindrome(n1));
	}

	@Test
	public void testB() {
//		输入: 1->2->2->1
//		输出: true

		ListNode n1 = new ListNode(1);
		ListNode n2 = n1.next = new ListNode(2);
		ListNode n3 = n2.next = new ListNode(2);
		ListNode n4 = n3.next = new ListNode(1);

		Assert.assertTrue(isPalindrome(n1));
	}

	// 我自己写的
	public boolean isPalindrome(ListNode head) {
		if (head == null || head.next == null) {
			return true;
		}
		List<Integer> list = new ArrayList<>();

		ListNode node = head;
		while (node != null) {
			list.add(node.val);
			node = node.next;
		}

		int offset = list.size() % 2 == 0 ? 0 : 1;//奇偶补偿
		int count  = list.size() / 2;
		for (int i = 0; i < count; i++) {
			int val0 = list.get(count - i - 1);
			int val1 = list.get(count + i + offset);

			if (val0 != val1) {
				return false;
			}
		}

		return true;
	}
}
